#include <iostream>
using namespace std;
#define int long long
const int MAXN = 1e9+1;
int f[MAXN] = {0,1};
void solve(int a, int b){
    int sum = 0;
    for(int i = a ; i <= b ; i ++){
        if(f[i] % 2 == 1) sum ++;
    }
    cout << sum;
}
void init(){
    for(int i = 2; i < MAXN ; i ++){
        f[i] = f[i - 1] + f[i - 2];
    }
}
signed main() {
    int a, b;
    init();
    int t;
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> t;
    while (t --) { // 注意 while 处理多个 case
        solve(a,b);
    }
}
// 64 位输出请用 printf("%lld")